
int knightDialer(int N) {
    static char jump[10][4] = {
    {2, 4, 6},
    {2, 6, 8},
    {2, 7, 9},
    {2, 4, 8},
    {3, 3, 9, 0},
    {0},
    {3, 1, 7, 0},
    {2, 2, 6},
    {2, 1, 3},
    {2, 2, 4}
    };

    if (N < 2) {
        return 10;
    }

    const int mod = (int)1e9 + 7;
    int **table = (int**)malloc(sizeof(int*) * 10);
//    int table[10][N] = {0};
    int ret = 0;

    for (int i = 0; i < 10; ++i) {
        table[i] = (int*)malloc(N * sizeof(int));
        memset(table[i], 0, N * sizeof(int));
        table[i][0] = 1;
    }

    for (int j = 1; j < N; j++) {
        for (int i = 0; i < 10; ++i) {
            for (char c = 0; c < jump[i][0]; ++c) {
                int to  = jump[i][c + 1];
                table[i][j] = (table[i][j] + table[to][j - 1]) % mod;
            }
        }
    }

    for (int i = 0; i < 10; ++i) {
        ret = (ret + table[i][N - 1]) % mod;
        free(table[i]);
    }
    free(table);
    return ret;
}
